﻿#pragma once

#ifdef _WIN32
#include <window.h>
#else
#include <sys/mman.h> // mmap
#include <unistd.h>	  // sysconf
#endif

#include <exception>
#include <unordered_map>
#include <map>
#include <iostream>
#include <time.h>
#include <assert.h>
#include <cstdlib>
#include <thread>
#include <mutex>
#include <algorithm>
#include <cstring>
#include "../ObjectPool/ObjectPool.h"

// 管理切分好的小对象的自由链表
static const int MAX_BYTES = 256 * 1024;
static const int NFREELISTS = 208;
static const int NPAGES = 129; // 用于在数组下标中构建1~128
static const int PAGE_SHIFT = 13;

#if defined(__x86_64__) | defined(_WIN64)
	typedef unsigned long long PAGE_TYPE;
#else
	typedef unsigned int PAGE_TYPE;
#endif

inline static void* SystemAlloc8KAligned(size_t kpage)
{
    const size_t user_8k = 8192;
    size_t len = kpage << PAGE_SHIFT;

    // 多申请一页，用于对齐
	#ifdef _WIN32
		void *raw = ::VirtualAlloc(0, len + user_8k, MEM_COMMIT | MEM_RESERVE,
							 PAGE_READWRITE); // 1 << 13 : 8 * 1024-->8KB
		if (raw == nullptr) throw std::bad_alloc();
	#else
		void* raw = ::mmap(nullptr, len + user_8k,
						PROT_READ | PROT_WRITE,
						MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);//::表示强制要求调用全局作用域中的mmap(即libc中的mmap),防止误调用
		if (raw == MAP_FAILED) throw std::bad_alloc();
	#endif
    
    // 计算偏移，向上对齐到 8 KB
    PAGE_TYPE addr  = (PAGE_TYPE)raw;
    PAGE_TYPE aligned = (addr + user_8k - 1) & ~(user_8k - 1);
    PAGE_TYPE  front_gap = aligned - addr;
    PAGE_TYPE  back_gap = user_8k - front_gap;
	
	#ifdef _WIN32
	////
	#else
    // 释放头部多余
    if (front_gap) ::munmap(raw, front_gap);
    // 释放尾部多余
    if (back_gap)  ::munmap((void*)(aligned + len), back_gap);
	#endif
	
    return (void*)aligned;
}

inline static void *SystemAlloc(size_t kpage)
{
	//返回虚拟地址空间,本质都是4KB对齐,并不关注用户逻辑页情况,此处我们要求能够8KB对齐,因此进行额外处理
	//32位,64位下都是4KB为最小粒度
	void* ptr = nullptr;
	try
	{
		ptr = SystemAlloc8KAligned(kpage);
	}
	catch(const std::exception& e)
	{
		std::cerr << e.what() << '\n';
	}
	return ptr;
}

inline static void SystemFree(void* ptr,size_t kPages)
{
	assert(ptr);
	#ifdef _WIN32
	::VirtualFree(ptr,0,MEM_RELEASE)
	#else
	int ret = ::munmap(ptr, kPages << PAGE_SHIFT);//成功返回0,失败返回-1
	// std::cout << ret << std::endl;
	// if(ret == -1)
	// {
	// 	std::cout << "munmap失败" << std::endl;
	// }
	#endif
}



class FreeList
{
public:
	//指针本身大小用于存放一个指针没有任何问题
	static void *&GetPtr(void *obj)
	{
		return *(void **)obj;
	}

public:
	void Push(void *obj)
	{
		//头插逻辑
		assert(obj);
		GetPtr(obj) = _freeList;
		_freeList = obj;
		_num++;
	}

	// push一段自由链表
	void PushRange(void *start, void *end,size_t n)
	{
		//头插逻辑
		GetPtr(end) = _freeList;
		_freeList = start;
		_num += n;
	}

	void *Pop()
	{
		assert(_freeList);
		void *obj = _freeList;
		_freeList = GetPtr(obj);
		_num--;
		return obj;
	}

	//弹出一段范围
	void PopRange(void*& start,void*& end,size_t n)
	{
		assert(n <= _num && _freeList);
		start = _freeList;
		end = start;
		for(size_t i = 0;i < n - 1;i++)
		{
			end = FreeList::GetPtr(end);
		}
		_freeList = FreeList::GetPtr(end);
		FreeList::GetPtr(end) = nullptr;
		_num -= n;
	}

	bool Empty()
	{
		return _freeList == nullptr;
	}

	size_t &MaxNum()
	{
		return _maxNum;
	}

	size_t Num()
	{
		return _num;
	}

	void SetWaterLevel(size_t highLevel,size_t lowLevel)
	{
		_highLevel = highLevel;
		_lowLevel = lowLevel;
	}

	size_t HighLevel()
	{
		return _highLevel;
	}
	
	size_t LowLevel()
	{
		return _lowLevel;
	}

private:
	void *_freeList = nullptr;
	size_t _maxNum = 1;//用于向CentralCache申请内存块数目的慢增长变量
	size_t _num = 0;//相应内存空间个数

	//规范thread_cache归还逻辑的高低水位
	size_t _highLevel = 0;//高水位
	size_t _lowLevel = 0;//低水位
	
};

// 计算对象大小的对齐映射规则
class SizeClass
{
public:
	// 对齐额外添加字节数,随申请空间的增大而增大:控制内存碎片消耗空间率(整体约保持在10%左右)和哈希桶个数
	// [1,128]              8byte对⻬      freelist[0,16)
	// [128+1,1024]         16byte对⻬     freelist[16,72)
	// [1024+1,8*1024]       128byte对⻬    freelist[72,128)
	// [8*1024+1,64*1024]    1024byte对⻬   freelist[128,184)
	// [64*1024+1,256*1024] 8*1024byte对⻬ freelist[184,208)
	static inline size_t _RoundUp(size_t size, size_t alignNum)
	{
		// size_t alignSize = size + (size % alignNum == 0 ? 0 : alignNum - size % alignNum);
		// size_t alignSize = size + (size % alignNum == 0 ? 0 : (size / alignNum + 1) * alignNum);

		// 介绍一种高明对齐写法
		return ((size + alignNum - 1) & ~(alignNum - 1)); // 非常巧妙
	}
	static inline size_t RoundUp(size_t size)
	{
		if (size <= 128)
		{
			return _RoundUp(size, 8);
		}
		else if (size <= 1024)
		{
			return _RoundUp(size, 16);
		}
		else if (size <= 8 * 1024)
		{
			return _RoundUp(size, 128);
		}
		else if (size <= 64 * 1024)
		{
			return _RoundUp(size, 1024);
		}
		else if (size <= 256 * 1024)
		{
			return _RoundUp(size, 8 * 1024);
		}
		else
		{
			// // 超出256*1024bytes
			// assert(false);
			return _RoundUp(size,8 * 1024);//同样按page对齐
		}
	}

	// 计算在哪一个桶中
	// static inline size_t _Index(size_t bytes, size_t align)
	//{
	//	return bytes % align == 0 ? bytes / align - 1 : bytes / align;
	// }

	// 另一种高明的写法
	static inline size_t _Index(size_t bytes, size_t align_shift)
	{
		return ((bytes + ((1 << align_shift) - 1)) >> align_shift) - 1;//下标对应减去1
	}

	static inline size_t Index(size_t size)
	{
		static int group_array[4] = {16, 56, 56, 56};
		if (size <= 128)
		{
			return _Index(size, 3);
		}
		else if (size <= 1024)
		{
			return _Index(size - 128, 4) + group_array[0];
		}
		else if (size <= 8 * 1024)
		{
			return _Index(size - 1024, 7) + group_array[1] + group_array[0];
		}
		else if (size <= 64 * 1024)
		{
			return _Index(size - 8 * 1024, 10) + group_array[2] + group_array[1] + group_array[0];
		}
		else if (size <= 256 * 1024)
		{
			return _Index(size - 64 * 1024, 13) + group_array[3] + group_array[2] + group_array[1] + group_array[0];
		}
		return -1;
	}

	// thread_cache一次从central_cache缓存获取多少空间
	static size_t NumMoveSize(size_t size)
	{
		assert(size > 0);

		int num = MAX_BYTES / size;
		// 如果size比较小,小内存,可能需求量大
		// 如果size比较大,大内存,可能需求量小

		// 框定上下限
		if (num < 2)
			num = 2;
		if (num > 512)
			num = 512;
		return num;
	}

	// central_cache从page_cache中获取Span大内存:page_cache中一页表示8KB
	static size_t NumMovePage(size_t alignSize, size_t batchNum)
	{
		// 同样需要收到thread_cache慢增长反馈调节的控制
		size_t npages = (alignSize * batchNum) >> PAGE_SHIFT;
		if (npages == 0)
			npages = 1;
		return npages;
	}
	//不受thread_cache慢增长反馈调节控制
	static size_t NumMovePage(size_t alignSize)
	{
		size_t batchNum = NumMoveSize(alignSize);
		size_t npages = (alignSize * batchNum) >> PAGE_SHIFT;
		if (npages == 0)
			npages = 1;
		return npages;
	}
};

// CentralCache结构中,管理内存的基本单位
struct Span
{
	PAGE_TYPE _pageId = 0; // 大块内存起始页的页号
	size_t _n = 0;		   // 页的数量
	size_t _alignSize = 0; 	   // 相应Span对应的对齐大小

	Span *_next = nullptr; // 双向链表结构
	Span *_prev = nullptr;

	size_t _useCount = 0;	   // 一个span中的大块内存切出的小块内存:被分配给thread_cache的计数,如果为0,说明完全未分配
	void *_freeList = nullptr; // 切好的小块内存的自由链表

	bool _isUse = false;//默认未被使用
};

class SpanList
//一个管理Span的双向循环链表
{
public:
	SpanList()
	{
		// _head = new Span;//这里使用new
		// _head->_next = _head;
		// _head->_prev = _head;
	}

	void DelayInitialize(ObjectPool<Span>& pool)
	{
		_head = pool.New();
		_head->_next = _head;
		_head->_prev = _head;
	}

	size_t Size()
	{
		return _size;
	}

	// 头插入逻辑
	void Insert(Span *pos, Span *newSpan)
	{
		assert(pos && newSpan);
		
		Span *prev = pos->_prev;
		prev->_next = newSpan;
		newSpan->_prev = prev;
		newSpan->_next = pos;
		pos->_prev = newSpan;
		_size++;
	}

	void Erase(Span *pos)
	{
		assert(pos && pos != _head);
		Span *prev = pos->_prev;
		Span *next = pos->_next;
		prev->_next = next;
		next->_prev = prev;

		pos->_prev = nullptr;
		pos->_next = nullptr;
		_size--;
		// 不需要delete pos:不需要,保存在相应span的_freeList中,通过_useCount判断使用情况,仅仅只是转移而已
	}

	void PushFront(Span *pos)
	{
		Insert(Begin(), pos); // 复用Insert
	}

	Span *PopFront()
	{
		Span *front = _head->_next;
		Erase(front); // 仅仅只是从链表中解除,但并未释放
		return front;
	}

	Span *Begin()
	{
		return _head->_next;
	}
	Span *End()
	{
		return _head;
	}

	// 判空逻辑
	bool Empty()
	{
		return _head == _head->_next;
	}

	std::mutex &GetMutex()
	{
		return _mtx;
	}

private:
	Span *_head = nullptr;	 // 作为哨兵位头结点
	std::mutex _mtx; // 桶锁
	size_t _size = 0;//链表中的Span个数
};
